home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / ZED3D095.ZIP / ZED3DSRC.ZIP / DRAWPOLY.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-19  |  6.4 KB  |  381 lines
  1. #include <drawpoly.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5.  
  6.  
  7. /*
  8.  * Note: the screen coordinate system is as follows:
  9.  *
  10.  * O------------>x+
  11.  * |
  12.  * |
  13.  * |
  14.  * |
  15.  * |
  16.  * |
  17.  * |
  18.  * \/y+
  19.  *
  20.  */
  21.  
  22. void init_edges(polygon *poly, outbuffer *out)
  23.     {
  24.     long a;
  25.     edge *e,*f;
  26.     long A,B,C,D;
  27.  
  28.  
  29.  
  30.     e=poly->edgetable; /* e will be current edge */
  31.     f=&e[poly->numedges-1]; /* previous edge */
  32.     poly->nextremove=0x7fffffff; /* initialize poly->nextremove */
  33.     /* start loop */
  34.     for(a=0;a<poly->numedges;a++)
  35.         {
  36.         /* transform from projection space to buffer space */
  37.         e->x1=proj2bufx(e->x1);
  38.         e->y1=proj2bufy(e->y1);
  39.         /* connect last edge to current edge */
  40.         f->y2=e->y1;
  41.         f->x2=e->x1;
  42.  
  43.         f=e; /* go to next edge */
  44.         e++;
  45.         }
  46.     }
  47.  
  48.  
  49.  
  50. void sort_edges(polygon *poly, outbuffer *out)
  51.     {
  52.     long a,b,c,x,y,z,counter;
  53.     edge *e, *f;
  54.  
  55.     e=poly->edgetable;
  56.     poly->inactive.next=0; /* empty inactive edge list */
  57.  
  58.     for(counter=0;counter<poly->numedges;e++,counter++)
  59.         {
  60.         /* ok, for each edge... */
  61.         /* ...sort endpoints */
  62.  
  63.         if(e->y1==e->y2)
  64.             {
  65.             /* RAAAAH! The dreaded edge parallel to the scanline, kill it! */
  66.             continue;
  67.             }
  68.  
  69.         if(e->y1>e->y2)
  70.             {
  71.             /* we should switch point 1 and 2 */
  72.             b=e->x1;
  73.             c=e->y1;
  74.             e->x1=e->x2;
  75.             e->y1=e->y2;
  76.             e->x2=b;
  77.             e->y2=c;
  78.             }
  79.         /* else, endpoints sorted ok */
  80.  
  81.         /* clip with top and bottom of screen */
  82.         if(e->y1>out->maxy)
  83.             {
  84.             continue;
  85.             }
  86.         if(e->y2<-out->maxy)
  87.             {
  88.             continue;
  89.             }
  90.  
  91.         if(e->y1<-out->maxy)
  92.             {
  93.             c=e->x1;
  94.  
  95.             e->x1=c+(e->x2-c)*(-out->maxy-e->y1)/(e->y2-e->y1);
  96.             e->y1=-out->maxy;
  97.  
  98.             if(e->y2>out->maxy)
  99.                 {
  100.                 e->x2=c+(e->x2-c)*(out->maxy-e->y1)/(e->y2-e->y1);
  101.                 e->y2=out->maxy;
  102.                 }
  103.             else if(e->y1==e->y2)
  104.                 {
  105.                 continue;
  106.                 }
  107.             }
  108.         else if(e->y2>out->maxy)
  109.             {
  110.             e->x2=(e->x2-e->x1)*(out->maxy-e->y1)/(e->y2-e->y1)+e->x1;
  111.             e->y2=out->maxy;
  112.             if(e->y1==e->y2)
  113.                 {
  114.                 continue;
  115.                 }
  116.             }
  117.  
  118.         /* ok now, calculate slope info */
  119.         x=e->x2-e->x1;
  120.         y=e->y2-e->y1;
  121.  
  122.         skipit:
  123.  
  124.         if(y<0)
  125.             {
  126.             x=-x;
  127.             y=-y;
  128.             }
  129.  
  130.  
  131.         e->increment=x/y;
  132.         e->numerator=x%y;
  133.         e->denominator=y;
  134.         if(x<0)
  135.             {
  136.             /* make sure we have a positive fraction as a remainder */
  137.             e->numerator+=y;
  138.             e->increment-=1;
  139.             }
  140.  
  141.         e->intercept=e->x1+out->maxx; /* initial intercept value */
  142.         e->run=0; /* clear run */
  143.  
  144.         /* ok now, perform insertion sort based on first scanline */
  145.         f=&poly->inactive;
  146.  
  147.         while((f->next)&&(f->next->y1<e->y1))
  148.             f=f->next;
  149.  
  150.         /* ok insert after f */
  151.         e->next=f->next;
  152.         f->next=e;
  153.         }
  154.     /* ok inactive list is all nice and tidy now */
  155.     }
  156.  
  157.  
  158.  
  159.  
  160. outbuffer *allocbuf(long maxx, long maxy)
  161.     {
  162.     outbuffer *b;
  163.     long s,a;
  164.  
  165.     /* allocate buffer */
  166.     b=malloc(sizeof(outbuffer));
  167.     if(!b) /* if malloc error */
  168.         return 0;
  169.  
  170.     /* initialize buffer struct */
  171.     b->maxx=maxx;
  172.     b->maxy=maxy;
  173.     b->width=(maxx<<1)+2;
  174.     b->height=(maxy<<1)+1;
  175.  
  176.     /* now, we want to allocate width*(height+1) elements for both zbuffer
  177.        and buffer */
  178.  
  179.     s=(b->height+1)*b->width; /* allocate s elements */
  180.  
  181.     b->buffer=malloc(s*sizeof(pixel));
  182.  
  183.     if(b->buffer==0)
  184.         {
  185.         destroybuf(b);
  186.         return 0;
  187.         }
  188.  
  189.     return b;
  190.     }
  191.  
  192.  
  193.  
  194. void destroybuf(outbuffer *out)
  195.     {
  196.     if(out)
  197.         {
  198.         if(out->buffer)
  199.             free(out->buffer);
  200.         out->buffer=0;
  201.         free(out);
  202.         }
  203.     }
  204.  
  205.  
  206. void update_lists(polygon *poly, long scanline)
  207.     {
  208.     edge *e,*f,*g;
  209.     long l;
  210.  
  211.     if(scanline>=poly->nextremove)
  212.         /* should we remove edges? */
  213.         {
  214.         l=0x7fffffff; /* yes, recalculate nextremove and remove edges */
  215.         e=&poly->active;
  216.         f=e->next;
  217.         while(f) /* so long as there are still edges to be examined... */
  218.             {
  219.             if(f->y2<=scanline)
  220.                 {
  221.                 f=f->next; /* remove edge */
  222.                 e->next=f;
  223.                 }
  224.             else
  225.                 {
  226.                 /* keep edge, test for nextremove */
  227.                 if(e->y2<l)
  228.                     l=e->y2; /* will be nextremove */
  229.                 e=f;
  230.                 f=f->next;
  231.                 }
  232.             }
  233.         poly->nextremove=l; /* store l into nextremove */
  234.         }
  235.  
  236.     while(g=poly->inactive.next,(g)&&(g->y1==scanline))
  237.         {
  238.         /* as long as we need to insert new edges */
  239.         /* recalculate nextsremove if necessary */
  240.         if(poly->nextremove>g->y2)
  241.             {
  242.             poly->nextremove=g->y2;
  243.             }
  244.  
  245.         e=&poly->active;
  246.         f=e->next;
  247.         while(f) /* insertion sort, most negative slope first */
  248.             {
  249.             if(f->intercept>=g->intercept)
  250.                 {
  251.                 if(f->intercept>g->intercept)
  252.                     {
  253.                     break;
  254.                     }
  255.                 else if(f->increment>=g->increment)
  256.                     {
  257.                     if(f->increment>g->increment)
  258.                         {
  259.                         break;
  260.                         }
  261.                     else if(f->numerator*g->denominator>
  262.                         g->numerator*f->denominator)
  263.                         {
  264.                         break;
  265.                         }
  266.                     }
  267.                 }
  268.             e=f;
  269.             f=f->next;
  270.             }
  271.  
  272.         /* insert g after e */
  273.         poly->inactive.next=g->next;
  274.         g->next=f;
  275.         e->next=g;
  276.         }
  277.     }
  278.  
  279.  
  280.  
  281. void update_intercept(polygon *poly)
  282.     {
  283.     edge *e;
  284.  
  285.     e=poly->active.next;
  286.  
  287.     while(e)
  288.         {
  289.         /* add integer part of fraction to current intercept value */
  290.         e->intercept+=e->increment;
  291.  
  292.         /* add fractional part to running total */
  293.         e->run+=e->numerator;
  294.         /* is the running total at least one? */
  295.         if(e->run>=e->denominator)
  296.             {
  297.             /* yes, decrease running total by one */
  298.             e->run-=e->denominator;
  299.             /* increase intercept value by one */
  300.             e->intercept++;
  301.             }
  302.  
  303.         /* next edge */
  304.         e=e->next;
  305.         }
  306.     }
  307.  
  308.  
  309.  
  310. void draw_spans(polygon *poly, outbuffer *out, long delta)
  311.     {
  312.     edge *e;
  313.     long a,b,x;
  314.     /* start with first span */
  315.  
  316.     e=poly->active.next;
  317.     while(e)
  318.         {
  319.         /* get the two endpoints of the span */
  320.         a=e->intercept;
  321.         e=e->next;
  322.         b=e->intercept;
  323.         e=e->next;
  324.  
  325.         if(b<0)
  326.             continue;
  327.         if(a>=out->width)
  328.             continue;
  329.  
  330.         if(a<0)
  331.             a=0;
  332.         if(b>=out->width)
  333.             b=out->width-1;
  334.  
  335.         /* blit span */
  336.         a+=delta;
  337.         b+=delta;
  338.         for(x=a;x<b;x++)
  339.             {
  340.             out->buffer[x]=poly->color;
  341.             }
  342.         }
  343.     }
  344.  
  345.  
  346.  
  347.  
  348. void drawpolygon(polygon *poly, outbuffer *out)
  349.     {
  350.     long scanline,delta,mode,a;
  351.  
  352.  
  353.     init_edges(poly,out);
  354.     sort_edges(poly,out);
  355.  
  356.  
  357.     if(poly->inactive.next)
  358.         {
  359.         /* initialize scanline to first scanline */
  360.         scanline=poly->inactive.next->y1;
  361.  
  362.         /* calculate delta */
  363.         delta=mulwidth(scanline+out->maxy);
  364.         poly->active.next=0;
  365.  
  366.  
  367.         /* loop until finished */
  368.         update_lists(poly,scanline);
  369.         while(poly->active.next)
  370.             {
  371.             update_intercept(poly);
  372.             draw_spans(poly,out,delta);
  373.  
  374.             /* go to next scanline */
  375.             scanline++;
  376.             delta+=out->width;
  377.             update_lists(poly,scanline);
  378.             }
  379.         }
  380.     }
  381.